package pro.softzhang.algo.lc200;

import pro.softzhang.algo.flag.knowledge.KBackTracking;
import pro.softzhang.algo.flag.theme.TMathCombination;

import java.util.ArrayList;
import java.util.List;

/**
 * 216. 组合总和 III
 * https://leetcode.cn/problems/combination-sum-iii
 */
@TMathCombination
public class LC216_CombinationSumIII {
    public static void main(String[] args) {

    }

    /**
     * 回溯解法
     */
    @KBackTracking
    static
    class Solution {
        private List<List<Integer>> cmbs = new ArrayList<>();

        public List<List<Integer>> combinationSum3(int k, int n) {
            return null;
        }

        private void backTrack(int num, List<Integer> cmb) {

        }
    }

    /**
     *
     */
    static
    class Solution1 {
        public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> path = new ArrayList<>(k);
            dfs(9, n, k, res, path);
            return res;
        }

        private void dfs(int i, int leftSum, int k, List<List<Integer>> res, List<Integer> path) {
            int d = k - path.size();

            // 剪枝
            if (leftSum < 0 || leftSum > (i * 2 - d + 1) * d / 2) {
                return;
            }

            if (d == 0) {
                res.add(new ArrayList<>(path));
                return;
            }

            for (int j = i; j >= d; j--) {
                path.add(j);
                dfs(j - 1, leftSum - j, k, res, path);
                path.remove(path.size() - 1);
            }
        }
    }
}
